package com.caochenlei.search;

public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90};
        System.out.println("10的index=" + insertValueSearch(arr, 10));
        System.out.println("50的index=" + insertValueSearch(arr, 50));
        System.out.println("90的index=" + insertValueSearch(arr, 90));
    }

    public static int insertValueSearch(int[] arr, int num) {
        return insertValueSearch(arr, 0, arr.length - 1, num);
    }

    public static int insertValueSearch(int[] arr, int left, int right, int num) {
        //如果没有找到
        if (left > right || num < arr[0] || num > arr[arr.length - 1]) {
            return -1;
        }
        //获取中间索引
        int mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left);
        //往左边递归找
        if (num < arr[mid]) {
            return insertValueSearch(arr, left, mid - 1, num);
        }
        //往右边递归找
        else if (num > arr[mid]) {
            return insertValueSearch(arr, mid + 1, right, num);
        }
        //数据位置找到
        else {
            return mid;
        }
    }
}
